﻿using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.Hash.LetterDysphorism
{
   //利用数组可以来当hash表
   //条件是已知数值大小且哈希值比较集中，否则容易浪费空间
    class LetterDysphorism
    {
        // =========================== 力扣242 有效的字母异位词
        //给定两个字符串s和t，编写一个函数来判断t是否是s的字母异位词
        //若s和t中每个字符出现的次数都行爱你沟通，则称s和t互为字母异位词
        //你可以假设字符串只包含小写字母
        public bool IsAnagram(string s, string t)
        {//数组其实就是一个简单哈希表，此题字符串只有小写字符，就可以定义一个数组，来记录字符串中字符出现的次数
            int[] record = new int[26];
            for(int i = 0;i< s.Length;i++)
            {//并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
                record[s[i] - 'a']++;//a的ASCII值最小，所以s[i] - 'a'必在0--25之间
            }
            for(int i = 0;i<t.Length;i++)
            {
                record[t[i] - 'a']--;
            }
            foreach(int i in record)
            {
                if (i != 0)//如果元素不为0，则说明字符串s和t一定是谁多了字符或者少了字符。
                    return false;
            }
            return true;
        }

        //======================== 力扣383 赎金信
        //给定一个赎金信(ransom)字符串和一个杂志(magazine)字符串，判断第一个字符串（ransom)能不能由第二个字符串(magazines）里面的字符构成。
        //为了不暴露赎金信自己，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
        //可以假设字符串只有小写字母
        public bool CanConstruct(string ransomNote,string magazine)
        {
            int[] record = new int[26];
            for(int i = 0;i<magazine.Length;i++)
            {
                //通过recode数据记录magazine里各个字符出现次数
                record[magazine[i] - 'a']++;
            }
            for (int i = 0; i < ransomNote.Length; i++)
            {
                //遍历ransomNode,在record里对应的字符个数做--操作
                record[ransomNote[i] - 'a']--;
                //如果小于零说明ransomNote里出现的字符，magazine没有
                if (record[ransomNote[i] - 'a'] < 0)
                    return false;

            }
            return true;
        }

        //======================= 力扣 49 字母异位词分组
        //给定一个字符串数组，将字母异位词组合在一起，可以按任意顺序返回结果列表
        //字母异位词只的是字母相同，但排列不同的字符
        //仅包含小写字母
        public IList<IList<string>> GroupAnagrams(string[] strs)
        {// 排序解法  将排序后的字符串作为哈希表的键
            Hashtable hashtable = new Hashtable();
            foreach (string str in strs)
            {
                char[] arr = str.ToCharArray();
                Array.Sort(arr);
                string key = new String(arr);
                List<string> ans;
                if (hashtable.ContainsKey(key))
                {
                    ans = (List<string>)hashtable[key];
                    hashtable.Remove(key);
                }
                else
                {
                    ans = new List<string>();
                }
                ans.Add(str);
                hashtable.Add(key, ans);
            }
            IList<IList<string>> tmp = new List<IList<string>>();
            ICollection value = hashtable.Values;
            foreach(List<string> str in value)
            {
                tmp.Add(str);
            }
            return tmp;
        }
        public IList<IList<string>> GroupAnagrams_1(string[] strs)
        {//计数解法，将每个字母出现的次数使用字符串表示，作为哈希表的值
            Hashtable hashtable = new Hashtable();
            foreach(string str in strs)
            {
                int[] counts = new int[26];
                int length = str.Length;
                for(int i = 0;i<length;i++)
                {
                    counts[str[i] - 'a']++;
                }
                //将每个出现次数大于0的字母和出现次数按顺序拼接成字符串，作为哈希表的键
                StringBuilder sb = new StringBuilder();
                for(int i = 0;i<26;i++)
                {
                    if(counts[i] != 0)
                    {
                        sb.Append((char)('a' + i));
                        sb.Append(counts[i]);
                    }
                }
                string key = sb.ToString();
                List<string> ans;
                if (hashtable.ContainsKey(key))
                {
                    ans = (List<string>)hashtable[key];
                    hashtable.Remove(key);
                }
                else
                {
                    ans = new List<string>();
                }
                ans.Add(str);
                hashtable.Add(key, ans);
            }
            IList<IList<string>> tmp = new List<IList<string>>();
            ICollection value = hashtable.Values;
            foreach (List<string> str in value)
            {
                tmp.Add(str);
            }
            return tmp;
        }
        
        //======================================== 力扣438 找到字符串中所有字母异位词
        //给定两个字符s和p，找到s中所有p的异位词子串，返回这些子串的其实索引。不考虑顺序
        public IList<int> findAnagrams(string s, string p)
        {//滑动窗口
            IList<int> res = new List<int>();
            int[] sArr = new int[26];
            int[] pArr = new int[26];

            int m = s.Length, n = p.Length;
            if (m < n)
                return new List<int>();
            //m必然大于n
            for (int i = 0;i<n;i++)
            {
                sArr[s[i] - 'a']++;
                pArr[p[i] - 'a']++;
            }
            for(int i = -1;i<m-n;i++)
            {
                if(i>=0)
                {
                    sArr[s[i] - 'a']--;
                    sArr[s[i+n] - 'a']++;
                }
                bool isAnagrams = true;
                for(int j = 0;j<26;j++)
                {
                    isAnagrams &= sArr[j] == pArr[j];
                    if (!isAnagrams)
                        break;
                }
                if (isAnagrams)
                    res.Add(i + 1);
            }
            return res;
        }







    }
}
